Операции над бинарными отношениями

1. **Булевы операции (дизъюнкция, конъюнкция, отрицание)**

Так как отношения — это множества, для них определены обычные теоретико-множественные операции.

**Дизъюнкция (объединение)**

R ∪ S = { (x, y) | (x, y) ∈ R или (x, y) ∈ S }
*Пример:* Если R = "быть братом", S = "быть сестрой", то R ∪ S = "быть родным братом или сестрой"

**Конъюнкция (пересечение)**

R ∩ S = { (x, y) | (x, y) ∈ R и (x, y) ∈ S }
*Пример:* Если R = "быть студентом", S = "жить в общежитии", то R ∩ S = "быть студентом, живущим в общежитии"

**Отрицание (дополнение)**

¬R = R⁻ = { (x, y) ∈ A × B | (x, y) ∉ R }
*Пример:* Если R = "быть женатым", то ¬R = "не быть женатым"

2. **Обращение (инверсия)**

R⁻¹ = { (y, x) | (x, y) ∈ R }
*Пример:* Если R = "быть родителем", то R⁻¹ = "быть ребенком"

**Свойства обращения:**
- (R⁻¹)⁻¹ = R
- (R ∪ S)⁻¹ = R⁻¹ ∪ S⁻¹
- (R ∩ S)⁻¹ = R⁻¹ ∩ S⁻¹

В матричном виде это транспонирование

3. **Композиция (суперпозиция)**

Пусть R ⊆ A × B, S ⊆ B × C. Тогда композиция:
R ∘ S = { (x, z) ∈ A × C | ∃y ∈ B: (x, y) ∈ R и (y, z) ∈ S }
*Пример:* Если R = "быть отцом", S = "быть родителем", то R ∘ S = "быть дедушкой"

**Свойства композиции:**
- Ассоциативность: (R ∘ S) ∘ T = R ∘ (S ∘ T)
- Дистрибутивность относительно объединения: R ∘ (S ∪ T) = (R ∘ S) ∪ (R ∘ T)
- Связь с обращением: (R ∘ S)⁻¹ = S⁻¹ ∘ R⁻¹

В матричном виде это булево умножение

4. **Возведение в степень**

Для отношения R на множестве A:

*Пример:* Если R = "быть родителем", то:
- R¹ = "быть родителем"
- R² = "быть дедушкой/бабушкой"
- R³ = "быть прадедушкой/прабабушкой"

**Свойства степеней:**
- Rᵐ ∘ Rⁿ = Rᵐ⁺ⁿ
- (Rᵐ)ⁿ = Rᵐⁿ